题目大意

题目链接

给你两个数k，n。n表示构造的序列的最小长度，k表示构造的序列满足下列两种算法得到的答案之差， 构造这个序列，若无，输出-1。

这个序列最多有1999个， 元素的绝对值小于1e6.

sum[i][j] 是指 a[i] 到 a[j]的和

算法1：
ans = max(ans, (r - l + 1) * sum[l][r])

算法2：

1
2
3
4
5
6
sum += a[i]
if sum < 0
    sum = 0
    left = i
else
    ans = max(ans, (i - left) * sum)

分析

首先你要明白这两种算法到底有什么不同。

举个例子 1 -2 2， 这个序列在算法1， 答案是3 ((1 - 2 + 2) * 3) ， 在算法2，答案是2(2 * 1), 这时候我们就可以按照前两项是1 -2， 后面全正来构造了。

假设前两项是1 -2， 假设后面m个元素的和为sum(后m个元素都是正的)， 那么对于算法1 ans1 = (m + 2) * (sum - 1)，算法2 ans2 = m * sum.

根据题意 ans1 - ans2 = k

1
2
3
4
(m + 2) * (sum - 1) - m * sum = k
m * sum - m + 2sum - 2 - m * sum = k
2sum - 2 = m + k
sum = (m + k) / 2 + 1

k是确定的，看m。

1
2
3
前提条件 m + 2 <= 1999 -> m < 1997
m + 2 >= n
然后 m + k 是偶数

这时候就呼之欲出了

1
2
3
当k为奇数时，m 是奇数 令 m = 1997
当k为偶数时，m是偶数 令 m = 1996
但是 k为偶数时，m是偶数时， m + 2 是 1998项，然后当n是1999时， 这就少了一项，怎么办？特判，在前面在加一个-1e6 即 -1e6 1 -2

m给出了， sum(sum = (m + k) / 2 + 1)也就求出来了，然后让后面的项之和为sum就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
power by Solo_Dance
*/
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}
vector<int>ans;

int main(){
    int t = read();
    while(t--){
        int k = read(), len = read();
        if (len >= 2000){
            puts("-1");
            continue;
        }
        ans.clear();
        int m;
        // 特判
        if (k % 2 == 0 && len == 1999){
            m = 1996;
            int sum = (k + m) / 2 + 1;
            while(sum > 1000000){
                ans.push_back(1000000);
                sum -= 1000000;
            }
            ans.push_back(sum);
            while(ans.size() < m) ans.push_back(0);
            cout << 1999 << "\n";
            cout << "-1000000 1 -2 ";
            for (auto c : ans) cout << c << " ";
            cout << "\n";
            continue;
        }

        // 给m赋值
        if (k & 1) m = 1997;
        else m = 1996;
        int sum = (k + m) / 2 + 1;
        while(sum > 1000000){
            ans.push_back(1000000);
            sum -= 1000000;
        }
        ans.push_back(sum);
        while(ans.size() < m) ans.push_back(0);
        cout << m + 2 << "\n";
        cout << "1 -2 ";
        for (auto c : ans) cout << c << " ";
        cout << "\n";
    }

    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。